/*************************************************************************
	> File Name: 503.下一个更大元素II.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/ 7 18:47:18 2021
 ************************************************************************/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElements(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    if (numsSize == 0) return NULL;

    int *res = (int *)malloc(sizeof(int) * numsSize);
    memset(res, -1, sizeof(int) * numsSize);
    //sta存储下标,利用取模的方式处理循环数组
    int sta[numsSize * 2], top = 0;
    for (int i = 0; i < numsSize * 2 - 1; i++) {
        while (top > 0 && nums[sta[top - 1]] < nums[i % numsSize]) {
            res[sta[top - 1]] = nums[i % numsSize];
            top--;
        }
        sta[top++] = i % numsSize;
    }
    return res;
}

